package lab02;

public class _01递归 {

    static int sum(int n) {

        if (n == 0)
            return 0;

        return n + sum(n - 1);
    }

    static int factorial(int n) {
        if (n == 0)
            return 1;

        return n * factorial(n - 1);
    }

    static void printi2j(int i, int j) {

        if (i > j) {

            System.out.println();
            return;
        }


        System.out.print(i);
        printi2j(++i, j);
    }

    static int sumArray(int[] a, int i) {

        if (i == a.length)
            return 0;

        return a[i] + sumArray(a, ++i);
    }

    static String reverseString(String str, int i) {
        if (i == str.length()) {
            return "";
        }

        return reverseString(str, ++i) + str.charAt(i - 1);

    }

    static int fibonacci(int n) {
        if (n == 1 || n == 2)
            return 1;

        return fibonacci(n - 1) + fibonacci(n - 2);
    }

    static int gcd(int m, int n) {

        if (m % n == 0)
            return n;

        return gcd(n, m % n);
    }


    static void insertSort(int[] a) {

        int len = a.length;
        int i = 0;
        int j = 0;

        for (i = 1; i < len; i++) {
            int pivot = a[i];

            // 找到i的位置j
            for (j = i - 1; j >= 0; j--) {
                if (a[j] < a[i]) {
                    break;
                }
            }

            // 后移
            for (int k = i - 1; k > j; k--) {

                a[k + 1] = a[k];
            }

            a[j + 1] = pivot;
        }
    }

    static void insertSort2(int[] a, int index) {

        if (index == a.length)
            return;

        int len = a.length;
        int i = index;
        int j = 0;

        int pivot = a[i];

        // 找到i的位置j
        for (j = i - 1; j >= 0; j--) {
            if (a[j] < a[i]) {
                break;
            }
        }

        // 后移
        for (int k = i - 1; k > j; k--) {

            a[k + 1] = a[k];
        }

        a[j + 1] = pivot;

        insertSort2(a, ++index);
    }

    static int binarySearch(int[] a, int n, int start, int end) {

        int mid = (start + end) / 2;

        if (n == a[mid])
            return mid;

        if (start == end)
            return -1;

        if (n > a[mid])
            return binarySearch(a, n, mid + 1, end);
        else
            return binarySearch(a, n, start, mid - 1);


    }

    static void hanoi(int n, int src, int dst, int helper) {


        if (n == 1) {

            System.out.println("Move: " + src + " -> " + dst);
            return;
        }

        hanoi(n - 1, src, helper, dst);
        System.out.println("Move: " + n + src + " -> " + dst);
        hanoi(n - 1, helper, dst, src);

    }

    public static void main(String[] args) {

        int[] a2 = {1, 2, 3, 5, 7, 9 };
        System.out.println(binarySearch(a2, 9, 0, a2.length - 1));

        hanoi(3, 0, 1, 2);
//        insertSort(a1);

        int[] a1 = {8, 9, 4, 6, 2, 3};
        insertSort2(a1, 1);
        System.out.println(a1);

        System.out.println(gcd(16, 24));

        System.out.println(fibonacci(5));

        String str = "hello, world!";
        System.out.println(reverseString(str, 0));

        System.out.println(sum(100));
        System.out.println(factorial(3));
        printi2j(0, 10);

        int[] a = {0, 1, 2, 3};
        System.out.println(sumArray(a, 0));
    }
}
